////Prim
//import java.util.Arrays;
//public class Main {
//    public static void main(String[] args) {
//        // 图的邻接矩阵
//        int[][] graph = {
//                {0, 2, 0, 6, 0},
//                {2, 0, 3, 8, 5},
//                {0, 3, 0, 0, 7},
//                {6, 8, 0, 0, 9},
//                {0, 5, 7, 9, 0}
//        };
//        // 调用Prim算法求最小生成树
//        prim(graph);
//    }
//
//    public static void prim(int[][] graph) {
//        int n = graph.length; // 顶点数
//        int[] key = new int[n]; // 记录每个顶点能连接的最小边权值
//        boolean[] visited = new boolean[n]; // 标记哪些顶点已加入生成树
//        int[] parent = new int[n]; // 记录最小生成树结构
//
//        // 初始化key数组为无穷大，表示暂时未知
//        Arrays.fill(key, Integer.MAX_VALUE);
//        key[0] = 0;       // 从顶点0开始构建MST
//        parent[0] = -1;   // 顶点0没有父节点
//
//        // 一共选n-1条边
//        for (int count = 0; count < n - 1; count++) {
//            // 贪心选择当前未访问中key值最小的点
//            int u = getMinKey(key, visited);
//            visited[u] = true;
//
//            // 遍历与u相邻的所有点，尝试更新它们的key
//            for (int v = 0; v < n; v++) {
//                if (graph[u][v] != 0 && !visited[v] && graph[u][v] < key[v]) {
//                    parent[v] = u;
//                    key[v] = graph[u][v]; // 更新更小的边
//                }
//            }
//        }
//        // 打印最小生成树
//        System.out.println("Prim算法最小生成树结果：");
//        System.out.println("边\t权重");
//        for (int i = 1; i < n; i++) {
//            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
//        }
//    }
//
//    //找到当前未访问中key值最小的顶点
//    public static int getMinKey(int[] key, boolean[] visited) {
//        int min = Integer.MAX_VALUE, minIndex = -1;
//        for (int i = 0; i < key.length; i++) {
//            if (!visited[i] && key[i] < min) {
//                min = key[i];
//                minIndex = i;
//            }
//        }
//        return minIndex;
//    }
//}


//Kruskal
import java.util.*;
// 边的类，实现Comparable接口便于排序
class Edge implements Comparable<Edge> {
    int src, dest, weight;
    public Edge(int s, int d, int w) {
        this.src = s;
        this.dest = d;
        this.weight = w;
    }

    // 按权重从小到大排序
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class Main {
    static int V = 5; // 顶点数
    public static void main(String[] args) {
        // 构建边集（无向图）
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 3, 6));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 8));
        edges.add(new Edge(1, 4, 5));
        edges.add(new Edge(2, 4, 7));
        edges.add(new Edge(3, 4, 9));

        // 执行Kruskal算法
        kruskal(edges);
    }

    public static void kruskal(List<Edge> edges) {
        // 排序所有边，权重小的排前面
        Collections.sort(edges);

        // 初始化并查集
        int[] parent = new int[V];
        int[] rank = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        List<Edge> result = new ArrayList<>(); // 存储最小生成树的边

        for (Edge edge : edges) {
            int x = find(parent, edge.src);
            int y = find(parent, edge.dest);

            // 如果加入这条边不会成环，则选它
            if (x != y) {
                result.add(edge);
                union(parent, rank, x, y); // 合并集合
            }

            // 当边数等于顶点数-1时就构建完毕
            if (result.size() == V - 1) break;
        }

        // 输出结果
        System.out.println("Kruskal算法最小生成树结果：");
        System.out.println("边\t权重");
        for (Edge edge : result) {
            System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);
        }
    }

    // 并查集查找根节点
    public static int find(int[] parent, int i) {
        if (parent[i] != i)
            parent[i] = find(parent, parent[i]);
        return parent[i];
    }

    // 合并两个集合
    public static void union(int[] parent, int[] rank, int x, int y) {
        int xRoot = find(parent, x);
        int yRoot = find(parent, y);

        if (rank[xRoot] < rank[yRoot])
            parent[xRoot] = yRoot;
        else if (rank[xRoot] > rank[yRoot])
            parent[yRoot] = xRoot;
        else {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
}

